#include"Heap.h"

void Swap(int* x, int* y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

void AdjustUp(HPDataType* a, int n)
{
	int child = n;
	int parent = (child-1)/2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}

	}
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * child + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapCreate(Heap* hp, HPDataType* m, int n)
{
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	hp->size = n;
	hp->capacity = n;
	memcpy(hp->a, m, sizeof(HPDataType) * n);
	/*for (int i = n - 1; i > 0; i--)
	{
		AdjustUp(hp->a, i);
	}*/

	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(hp->a, n, i);
	}

}

void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void Expansion(Heap* hp)
{
	int newcapacity =hp->capacity==0?4: hp->capacity * 2;
	HPDataType* temp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
	if (temp == NULL)
	{
		perror("realloc failed");
		exit(-1);
	}
	hp->a = temp;
	hp->capacity = newcapacity;
}

void HeapPush(Heap* hp, HPDataType x)
{
	if (hp->size == hp->capacity)
	{
		Expansion(hp);
	}
	hp->a[hp->size++] = x;
	AdjustUp(hp->a, hp->size-1);
}

HPDataType HeapTop(Heap* hp)
{
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	return hp->size;
}

bool HeapEmpty(Heap* hp)
{
	return hp->size == 0;
}

void HeapPrint(Heap* hp)
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d  ", hp->a[i]);
	}
	printf("\n");
}

void HeapSort(Heap* hp)
{
	for (int i = hp->size - 1; i > 0; i--)
	{
		Swap(&hp->a[0], &hp->a[i]);
		AdjustDown(hp->a, i-1, 0);
	}
	HeapPrint(hp);
}



